3258. Последовательность Фибоначчи

Последовательность Фибоначчи задана следующим образом:

a₀ = 0

a₁ = 1

a_k = a_k-1 + a_k-2

Для заданного числа n найдите значение n-го элемента a_n последовательности Фибоначчи.

Вход. Одно натуральное число n (1 ≤ n ≤ 40).

Выход. Выведите n-ый элемент последовательности Фибоначчи.

Пример входа 1	Пример выхода 1
2	1
Пример входа 2	Пример выхода 2
5	5

РЕШЕНИЕ

числа Фибоначчи

Анализ алгоритма

В данной задаче следует найти n-ое число Фибоначчи. При n ≤ 40 рекурсивная реализация пройдет по времени. Последовательность Фибоначчи имеет вид:

Наибольшим числом Фибоначчи, которое повещается в тип int является

f₄₆ = 1836311903

При n ≤ 40 достаточно использовать тип данных int.

Пусть функция fib(n) вычисляет n-ое число Фибоначчи. Тогда имеем следующее рекуррентное соотношение:

fib(n) =

Реализация алгоритма

Функция fib вычисляет n-ое число Фибоначчи.

int fib(int n)

{

if (n == 0) return 0;

if (n == 1) return 1;

return fib(n - 1) + fib(n - 2);

}

Основная часть программы. Читаем значение n, вычисляем и выводим fib(n).

scanf("%d", &n);

printf("%d\n", fib(n));

Java реализация

import java.util.*;

public class Main

{

static int f(int n)

{

if (n == 0) return 0;

if (n == 1) return 1;

return f(n-1) + f(n - 2);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

System.out.println(f(n));

con.close();

}

}

Python реализация – мемоизация

Функция fib вычисляет n-ое число Фибоначчи.

def fib(n):

if dp[n] != -1:

return dp[n]

dp[n] = fib(n - 1) + fib(n - 2)

return dp[n]

Основная часть программы. Читаем входное значение n.

n = int(input())

Инициализируем список dp.

dp = (n + 1) * [-1]

dp[0] = 0

dp[1] = 1

Вычисляем и выводим ответ.

print(fib(n))

Python реализация – мемоизация 2

arr = {}

Функция fib вычисляет n-ое число Фибоначчи.

def fib(n):

if (n == 0): return 0

if (n == 1): return 1

if n not in arr:

arr[n] = fib(n - 1) + fib(n - 2)

return arr[n]

Основная часть программы. Читаем значение n, вычисляем и выводим fib(n).

n = int(input())

print(fib(n))

Python реализация – мемоизация 3

arr = {0:0, 1:1}

Функция fib вычисляет n-ое число Фибоначчи.

def fib(n):

if arr.get(n) is None:

arr[n] = fib(n - 1) + fib(n - 2)

return arr[n]

Основная часть программы. Читаем значение n и выводим fib(n).

n = int(input())

print(fib(n))

Python реализация – TLE

Функция fib вычисляет n-ое число Фибоначчи.

def fib(n):

if (n == 0): return 0

if (n == 1): return 1

return fib(n - 1) + fib(n - 2)

Основная часть программы. Читаем значение n, вычисляем и выводим fib(n).

n = int(input())

print(fib(n))